/*
 * @lc app=leetcode.cn id=456 lang=javascript
 *
 * [456] 132模式
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function (nums) {
  const n = nums.length;
  const left = new Array(n).fill(Number.POSITIVE_INFINITY);

  // 任意位置左边最小元素
  for (let i = 1; i < n; i++) {
    left[i] = Math.min(left[i - 1], nums[i - 1]);
  }

  const stack = [];
  for (let j = n - 1; j >= 0; j--) {
    let right = Number.NEGATIVE_INFINITY;
    // nums[j]大于栈顶的话，出栈，栈中最大的元素赋值给right
    while (stack.length && nums[j] > stack[stack.length - 1]) {
      right = stack.pop();
    }
    // 当前j位置的左边最小元素小于right的话，就是132模式 nums[i]<nums[j]>nums[k]
    if (left[j] < right) return true;
    stack.push(nums[j]);
  }

  return false;
};
// @lc code=end
